Conventional computer systems may include multiple processors that operate in parallel to execute multiple different programs or execution threads. Multi-threaded execution environments typically control the flow of work requests via a queue. A queue of execution threads may in some cases be described as a logically circular contiguous array, where the producers and consumers of the work requests use an array index to identify a particular work request. In multi-threaded environments, multiple work requests may be identified by using a “two-tuple” of a start-index value and an end-index value to specify a “range” of contiguous array indices.
However, conventional array-based solutions for tracking execution threads may experience a performance bottleneck when attempting to compute the next available array index for a range of array indices for multi-thread execution environments. Common solutions typically rely on either a “worker thread” or statically allocated index ranges. For example, if all work requests are processed by a single worker thread, then the system may guarantee that the next available array index is unique while multiple threads are being serviced. One disadvantage of this mechanism is that the worker thread is event driven and thus must sleep and wake up, thereby negatively affecting aggregate system performance due to latency. Another disadvantage is that the multithreaded clients of the worker-thread will also experience unnecessary serialization for a portion of their work request processing.
Similarly, if a multi-threaded processing implementation chooses to statically allocate ranges of array indices then two issues may arise. One issue is the need to calculate what size all of the ranges should be. Another issue is deciding what happens if there are not enough work requests in the input stream to completely fill a range. Conventional systems typically attempt to address the first issue by allowing a user to coarsely “tune” the range size by modifying a documented program variable. Conventional systems may attempt to address the second issue by arming a timer that may flush a range if the range is only partially filled. However, both of these attempts to solve their respective issues typically fail due to the static nature of the range size and the timeout duration of the system. When using conventional solutions, system administrators can only hope to specify tunable parameters that are “good enough” and thus the solutions will never be optimal.